

#ifndef UD_GRAPH_H
#define UD_GRAPH_H 1

#include "zdbmain.h"

#pragma pack (push, 8)

class UcDbGraph;

class UcDbGraphNode : public UcHeapOperators
{
friend class UcDbGraph;

public:
    UcDbGraphNode(void* pData = NULL);
    virtual ~UcDbGraphNode();

    enum Flags    { kNone		= 0x00,
		    kVisited		= 0x01,   
		    kOutsideRefed	= 0x02,   
		    kSelected		= 0x04,   
		    kInList		= 0x08,   
		    kListAll		= 0x0E,   
		    kFirstLevel		= 0x10,   
		    kUnresTree		= 0x20,   
		    kAll		= 0x2F };

    void*		data		() const;
    void		setData		(void*);

    int			numOut		() const;
    int			numIn		() const;

    UcDbGraphNode*	in		(int) const;
    UcDbGraphNode*	out		(int) const;

    Ucad::ErrorStatus	addRefTo	(UcDbGraphNode*);
    Ucad::ErrorStatus	removeRefTo	(UcDbGraphNode*);
    Ucad::ErrorStatus	disconnectAll	();

    UcDbGraph*		owner		() const;

    bool                isMarkedAs      (ZSoft::UInt8 flags) const;
    Ucad::ErrorStatus	markAs		(ZSoft::UInt8 flags);
    Ucad::ErrorStatus	clear		(ZSoft::UInt8 flags);

    Ucad::ErrorStatus   markTree	(ZSoft::UInt8 flags,
                                         UcDbVoidPtrArray* = NULL);

    int			numCycleOut	() const;
    int			numCycleIn	() const;

    UcDbGraphNode*	cycleIn		(int) const;
    UcDbGraphNode*	cycleOut	(int) const;

    UcDbGraphNode*	nextCycleNode	() const;

    bool                isCycleNode     () const;

	void			setEdgeGrowthRate(int outEdgeRate, int inEdgeRate);

private:

    UcDbGraphNode(const UcDbGraphNode&);
    UcDbGraphNode&	operator =	(const UcDbGraphNode&);

    UcDbVoidPtrArray	mOutgoing;
    UcDbVoidPtrArray	mIncoming;

    void*		mpData;

    void		setFirstLevel	(ZSoft::Boolean);

    ZSoft::UInt8	mFlags;

    Ucad::ErrorStatus	setOwner	(UcDbGraph*);
    Ucad::ErrorStatus	resetCycles	();
    Ucad::ErrorStatus	removeCycleRefTo (UcDbGraphNode*);
    Ucad::ErrorStatus   clearCycles	();

    UcDbGraph*		mpOwner;

    UcDbVoidPtrArray*	mpCycleOut;
    UcDbVoidPtrArray*	mpCycleIn;
};

class UcDbGraph : public UcHeapOperators
{
friend class UcDbGraphNode;

public:
    UcDbGraph(UcDbGraphNode* pRoot = NULL);
    virtual ~UcDbGraph();

    UcDbGraphNode*	node		(int index) const;
    UcDbGraphNode*	rootNode	() const;

    int			numNodes	() const;
    bool                isEmpty         () const;

    Ucad::ErrorStatus	addNode		(UcDbGraphNode*);
    Ucad::ErrorStatus	addEdge		(UcDbGraphNode* pFrom,
                                         UcDbGraphNode* pTo);

    Ucad::ErrorStatus	delNode		(UcDbGraphNode*);

    void		reset		();
    void		clearAll	(ZSoft::UInt8 flags);

    void		getOutgoing	(UcDbVoidPtrArray&);

    virtual ZSoft::Boolean findCycles	(UcDbGraphNode* pStart = NULL);
    Ucad::ErrorStatus	breakCycleEdge	(UcDbGraphNode* pFrom,
                                         UcDbGraphNode* pTo);

    void		setNodeGrowthRate(int rate);

protected:

    Ucad::ErrorStatus	clearAllCycles	();

private:

    UcDbGraph(const UcDbGraph&);
    UcDbGraph&		operator =	(const UcDbGraph&);

    UcDbVoidPtrArray	mNodes;

    UcDbVoidPtrArray*	mpCycleNodes;

    void		setDirty	();
    bool                mDirty;

};

class UcDbGraphStack : public UcHeapOperators
{
public:
    UcDbGraphStack(int initPhysicalLength = 0, int initGrowLength = 8);
    ~UcDbGraphStack();

    Ucad::ErrorStatus	push		(UcDbGraphNode*);
    UcDbGraphNode*	pop		();

    UcDbGraphNode*	top		() const;

    bool                isEmpty         () const;

private:

    UcDbVoidPtrArray	mStack;
};

inline void* UcDbGraphNode::data() const { return mpData; }
inline void UcDbGraphNode::setData(void* pData) { mpData = pData; }

inline int UcDbGraphNode::numOut() const { return mOutgoing.length(); }
inline int UcDbGraphNode::numIn() const { return mIncoming.length(); }

inline UcDbGraphNode* UcDbGraphNode::in(int idx) const
    { return (UcDbGraphNode*)mIncoming.at(idx); }
inline UcDbGraphNode* UcDbGraphNode::out(int idx) const
    { return (UcDbGraphNode*)mOutgoing.at(idx); }

inline bool UcDbGraphNode::isMarkedAs(ZSoft::UInt8 flag) const
    { return (this->mFlags & flag) != 0; }

inline UcDbGraph* UcDbGraphNode::owner() const { return mpOwner; }
inline Ucad::ErrorStatus UcDbGraphNode::setOwner(UcDbGraph* pOwn)
    { assert(!mpOwner); if (mpOwner) return Ucad::eInvalidOwnerObject;
        mpOwner = pOwn; return Ucad::eOk; }

inline int UcDbGraphNode::numCycleOut() const
    { return mpCycleOut == NULL ? 0 : mpCycleOut->length(); }
inline int UcDbGraphNode::numCycleIn() const
    { return mpCycleIn == NULL ? 0 : mpCycleIn->length(); }

inline UcDbGraphNode* UcDbGraphNode::cycleOut(int idx) const
    { return (UcDbGraphNode*)
	 (mpCycleOut == NULL ? NULL : mpCycleOut->at(idx)); }
inline UcDbGraphNode* UcDbGraphNode::cycleIn(int idx) const
    { return (UcDbGraphNode*)
	 (mpCycleIn == NULL ? NULL : mpCycleIn->at(idx)); }

inline UcDbGraphNode* UcDbGraphNode::nextCycleNode() const
    { assert(mpCycleOut != NULL); return cycleOut(0); }

inline bool UcDbGraphNode::isCycleNode() const
    { return mpCycleIn != NULL || mpCycleOut != NULL; }
inline int UcDbGraph::numNodes() const { return mNodes.length(); }
inline UcDbGraphNode* UcDbGraph::node(int idx) const
    { return (UcDbGraphNode*)mNodes.at(idx); }

inline UcDbGraphNode* UcDbGraph::rootNode() const
    { return (numNodes() > 0) ? node(0) : NULL; }

inline bool UcDbGraph::isEmpty() const
    { return numNodes() == 0; }

inline void UcDbGraph::setDirty() { mDirty = true; }

inline bool UcDbGraphStack::isEmpty() const
    { return mStack.isEmpty(); }

inline UcDbGraphNode* UcDbGraphStack::top() const
    { return isEmpty() ? NULL : (UcDbGraphNode*)mStack.last(); }

#pragma pack (pop)

#endif

